Date: Tue, 10 Dec 1996 16:48:51 GMT
Server: NCSA/1.4.2
Content-type: text/html

<HTML>
<HEAD>
<TITLE>CSE 373 Midterm topics</TITLE>
</HEAD>

<BODY>
<H1>CSE 373 Midterm topics</H1>

The midterm examination on Wednesday, October 30 will cover
the following topics.  Nearly all of these are covered in
the text in the associated chapters.

<p>

<pre>
Chapter 1
  Abstract data type.
  Data structure.
  Encapsulation.

Chapter 2
  Sets: notation, standard operations, Cartesian product.
  Linear order (also called total order).
  Permutations, factorial, Stirling's formula.
  Generating random permutations in C++ (e.g., see p22).
  Boolean variables, floor and ceiling, modulus operator.
  Logarithms and their properties.
  Recursion, recursive factorial in C++, recursive Towers of Hanoi.
  Summations and recurrences, sum of first n integers.
  Sum of first n squares, Fibonacci sequence.
  Proof by contradiction.  Proof by induction.
  
Chapter 3
  Running time formulations in terms of input size n and constants:
    e.g., T(n) = cn.
  Largest value sequential search in C++ (e.g., see p43).
  Constant, linear, quadratic, cubic and exponential running times.
  Big-Oh, big-Omega, and big-Theta definitions, notations.
  Simplifying big-Oh expressions.
  Calculating running times of programs.
  Binary search.
  Ordering functions by their growth rates.

Chapter 4
  Lists and the ADT on p81.
  Comparison of array and pointer implementations of lists.
  Freelists, doubly linked lists.
  Stack ADT,  Queue ADT.

Chapter 5
  Binary tree, depth, height, full binary tree, complete binary tree.
  Full binary tree theorem.
  Binary tree node ADT (e.g., see p126).
  Preorder, inorder, and postorder traversal.
  Space requirements for pointer-based impl. of binary trees.
  Array implementation for complete binary trees.
  Huffman trees, encoding and decoding with Huffman trees.
  Prefix property of codes, efficiency of a Huffman code.
  Binary search tree property.
  Searching for an element in a BST (the find and findhelp methods).
  Insertion and deletion in a BST.
  Heap data structure and its use in implementing the priority queue.
  Siftdown and Buildheap operations.  Time required to build the heap.

Chapter 6
  Parent pointer implementation of general trees.
  Implementation of FIND and UNION operations.
  Path compression.

Chapter 7
  Terminology for graphs.
  Comparison of adjacency matrix and adjacently list implementations.

</pre>

</BODY>
Last updated 25 October 1996 by S. Tanimoto
</HTML>
